1. Field of the Invention
This invention relates to a coding method and apparatus therefor, particularly a method and apparatus for coding image data. By way of example, the invention is used in still-picture hierarchical coding employed in an image-data service or still-picture filing apparatus.
2. Description of the Related Art
In a facsimile machine, which is a typical example of a still-picture communication apparatus, a binary image is coded using MH or MR coding. These coding methods require that all of the image data be transmitted in order to grasp the entirety of the image. Consequently, in an image-data service, such as a video data-base service or VIDEOTEX, in which it is required that an image be judged in rapid fashion, difficulties are encountered in employing the coding methods used in an apparatus such as a facsimile machine.
Accordingly, in the transmission of a single image, a sequential reproduction method has been proposed in which rough image information is transmitted initially, after which additional information is transmitted to gradually form a detailed image. Coding for the purpose of achieving this is hierarchical coding.
In sequential reproduction, there are many instances in which rough information employs information obtained by reducing the size of the original image. A hierarchy is formed by repeating this reduction processing a number of times. For example, if reduction processing for reduction at a ratio of 1/2 in the horizontal and vertical directions is applied to an image and then this processing is repeated, images having areas of 1/4 and 1/16 will be formed. In sequential reproduction, first data representing the small image of size 1/16 is coded and transmitted, next additional information for forming the image of size 1/4 from the image of size 1/16 is coded and transmitted, and then additional information for forming the original image from the image of size 1/4 is transmitted.
In order to record the 1/4 and 1/16 images at a size the same as that of the original image, the images are outputted upon lowering recording density to 1/2 and 1/4.
Reducing the additional information by as much as possible is very effective in curtailing transmission time. Accordingly, a large number of proposals concerning coding preprocessing have been considered, namely preprocessing in which portions of an image having a much larger size that can be predicted from an image of a smaller size are excluded from coding.
Typical prediction (hereinafter referred to as "TP") is an effective means of performing such coding preprocessing.
According to TP, two-lines, for example, are adopted as a block line. If a 2.times.2 array of four pixels to be coded, the reduced pixel corresponding to these pixels and the peripheral pixels surrounding it, for a total of nine pixels, are of the same color, then the 2.times.2 array of pixels are capable of TP. Accordingly, the 2.times.2 array of pixels are excluded from coding.
More specifically, a TP flag attached to the beginning of a block line is made "0" if a pixel that is the object of coding is capable of TP based upon the reduced pixel. If there is an exception and TP is impossible, then the TP flag is made "1" With-regard to a block line for which the TP flag is "0", a pixel capable of TP is excluded from coding and all other pixels are subjected to the usual coding. In case of block lines for which the TP flag is "1", all of the pixels are subjected to the usual coding.
Deterministic prediction (hereinafter referred to as "DP") also is an effective means of performing coding preprocessing.
According to DP, if there is a rule that has been decided as a method of reducing an image, then a pixel, which is the object of coding, and whose on/off state (i.e., a pixel value of "1" or "0") can be predicted from a reduced pixel (low-resolution pixel data) and surrounding pixels (high-resolution pixel data) of the pixel which is the object of coding by making a reverse inference from the rule, is extracted in advance. If the pixel which is the object of coding is one that can be uniquely determined at the time of coding, this pixel is excluded from coding. At decoding, the on/off state of a pixel which is the object of decoding is uniquely determined from the low-resolution pixel data and high-resolution pixel data already decoded.
However, certain problems arise in the techniques described above.
Specifically, in coding using TP, it is necessary to judge whether TP is possible or not. In order to make this judgment, pixels which are the object of coding, a reduced pixel corresponding to these pixels and pixels surrounding this reduced pixel must be investigated every block line by prescanning, and it is required that the TP flag be attached to the beginning of each block line. Consequently, in coding using TP, it is necessary to refer to reduced pixels and the peripheral pixels a number of times. The hardware required to accomplish this is very complicated.
In coding using DP, as illustrated in FIG. 23, first the entire image is subjected to reduction processing at step S1000, the entirety of the reduced image is stored temporarily in a frame memory, and then DP is performed at step S1001. As a result, processing takes time. In addition, since a frame memory for storing the reduced image is required, a greater amount of hardware is necessary.
Furthermore, as set forth in the ISO/IEC (Committee Draft 11544, etc.), a plurality of means for raising coding efficiency are successively applied to each item of image data in order, after which predictive coding is performed. In order to accomplish this, processing is executed by an arrangement of the kind shown in FIG. 34. To describe this, TP for minimum resolution set forth in ISO/IEC (Committee Draft 11544, etc.) will be taken as an example.
According to TP for minimum resolution, if the image on a line presently undergoing coding is identical with the entirety of the image on the line immediately above it, a prediction flag, which indicates whether a hit has been attained with regard to a prediction, is coded and the image data is excluded from coding. On the other hand, if the image on a line presently undergoing coding differs by even one pixel from the image on the line immediately above it, a prediction flag indicating that the prediction was erroneous is coded and the image data is coded as well.
An arrangement for implementing this processing will be described with reference to FIG. 34.
As shown in FIG. 34, an image data memory 500 delivers its output to a block 501 that executes TP processing. The results of TP processing enter a prediction-flag memory 502, the output of which is applied to a prediction coder 503. The latter outputs a code.
Binary image data which is the object of coding is stored in the image data memory 500. The TP block 501 reads image data, in sets of two lines each, out of the image data memory 500 and, if agreement with a prediction is achieved, writes a flag indicative of agreement with the prediction in the prediction-flag memory 502.
The prediction coder 503 reads image data out of the image data memory 500 and the prediction flag out of the prediction-flag memory 502. If agreement with a prediction is achieved, only the prediction flag is coded and the line thereof is excluded from the object of coding. If there is no agreement with a prediction, the prediction coder 503 codes the prediction flag and successively codes the pixels of this line, thereby outputting a code.
Though the foregoing description relates to TP as an example, a code output can be obtained by similar processing even with another arrangement having means for raising prediction efficiency or means for performing a resolution transformation.
A problem encountered in the technique described above is that coding processing cannot start until the processing performed by the means for raising coding efficiency or by the means for performing resolution conversion no longer has an effect upon the coder. This means that the technique does not lend itself to synchronous coding on a real-time basis.